package 搜索.DFS;

import java.util.ArrayList;
import java.util.List;
/*
解题思路：
        该题也是求可达性的一种问题，所以要用DFS来解决。加上本题和695十分相似，于是只要稍加改动就可以了。
        695是求岛屿最大面积，当时的做法是得到一个岛屿的面积就存到res，然后和下一个岛屿的面积相比较，只保留最大的那个
        岛屿面积在res中。
        试想一下，你每得到一个岛屿的面积就意味着那肯定有一个岛。该题要我们求岛的数量，我们就可以把每一个岛的岛屿面积存入一个LIST
        到时候LIST中有几个数据 不就证明有几个岛。
 */
public class 岛屿数量_200 {


    public static void main(String[] args) {
        岛屿数量_200 岛屿数量_200 = new 岛屿数量_200();

        char[][] grid = new char[][]{
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };


        System.out.println(岛屿数量_200.numIslands(grid));
    }

    public int numIslands(char[][] grid) {

        if (grid.length == 0) {
            return 0;
        }

        List<Integer> res = new ArrayList<>();//用来存放结果

        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == '1') {
                    int area = DFS(grid, r, c);
                    res.add(area);//把每个岛屿的面积都添加岛res中
                }
            }


        }
        return res.size();
    }


    public int DFS(char[][] grid, int r, int c) {
        if (!(0 <= r && r < grid.length && 0 <= c && c < grid[0].length)) {//超出了边缘，走不下去了
            return 0;
        }

        if (grid[r][c] != '1') {//不是岛屿也返回，因为岛屿要相连的1，一旦出现0就要返回
            return 0;
        }

        grid[r][c] = '0';//沉岛

        int area = 1;

        area += DFS(grid, r - 1, c);//向上遍历
        area += DFS(grid, r + 1, c);//向下遍历
        area += DFS(grid, r, c - 1);//向左遍历
        area += DFS(grid, r, c + 1);//向右遍历


        return area;
    }
}
